{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Decrease Elements To Make Array Zigzag"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: movesToMakeZigzag"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #递减元素使数组呈锯齿状"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组&nbsp;<code>nums</code>，每次 <strong>操作</strong>&nbsp;会从中选择一个元素并 <strong>将该元素的值减少&nbsp;1</strong>。</p>\n",
    "\n",
    "<p>如果符合下列情况之一，则数组&nbsp;<code>A</code>&nbsp;就是 <strong>锯齿数组</strong>：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>每个偶数索引对应的元素都大于相邻的元素，即&nbsp;<code>A[0] &gt; A[1] &lt; A[2] &gt; A[3] &lt; A[4] &gt; ...</code></li>\n",
    "\t<li>或者，每个奇数索引对应的元素都大于相邻的元素，即&nbsp;<code>A[0] &lt; A[1] &gt; A[2] &lt; A[3] &gt; A[4] &lt; ...</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>返回将数组&nbsp;<code>nums</code>&nbsp;转换为锯齿数组所需的最小操作次数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [1,2,3]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>我们可以把 2 递减到 0，或把 3 递减到 1。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [9,6,1,6,2]\n",
    "<strong>输出：</strong>4\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [decrease-elements-to-make-array-zigzag](https://leetcode.cn/problems/decrease-elements-to-make-array-zigzag/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [decrease-elements-to-make-array-zigzag](https://leetcode.cn/problems/decrease-elements-to-make-array-zigzag/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3]', '[9,6,1,6,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToMakeZigzag(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans1 = ans2 = 0\n",
    "        copy = nums\n",
    "        for i in range(0, n, 2):\n",
    "            tmp = 0\n",
    "            if i - 1 >= 0:\n",
    "                tmp = max(tmp, nums[i] - nums[i - 1] + 1)\n",
    "            if i + 1 < n:\n",
    "                tmp = max(tmp, nums[i] - nums[i + 1] + 1)\n",
    "            ans1 += tmp\n",
    "        nums = copy\n",
    "        for i in range(1, n, 2):\n",
    "            tmp = 0\n",
    "            if i - 1 >= 0:\n",
    "                tmp = max(tmp, nums[i] - nums[i - 1] + 1)\n",
    "            if i + 1 < n:\n",
    "                tmp = max(tmp, nums[i] - nums[i + 1] + 1)\n",
    "            ans2 += tmp\n",
    "        return min(ans1, ans2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToMakeZigzag(self, nums: List[int]) -> int:\n",
    "        s = [0] *2\n",
    "        for i,x in enumerate(nums):\n",
    "            left = nums[i-1] if i else inf\n",
    "            right = nums[i+1] if i<len(nums) - 1 else inf\n",
    "            s[i%2] += max(nums[i] - min(left, right) +1, 0)\n",
    "        return min(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToMakeZigzag(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        def f(pos: int) -> int:\n",
    "            res = 0\n",
    "            for i in range(pos, n, 2):\n",
    "                tmp = 0\n",
    "                if i - 1 >= 0:\n",
    "                    tmp = max(tmp, nums[i] - nums[i - 1] + 1)\n",
    "                if i + 1 < n:\n",
    "                    tmp = max(tmp, nums[i] - nums[i + 1] + 1)\n",
    "                res += tmp\n",
    "            return res\n",
    "        return min(f(0), f(1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToMakeZigzag(self, nums: List[int]) -> int:\n",
    "        s = [0] * 2\n",
    "        for i, x in enumerate(nums):\n",
    "            left = nums[i - 1] if i else inf\n",
    "            right = nums[i + 1] if i < len(nums) - 1 else inf\n",
    "            s[i % 2] += max(x - min(left, right) + 1, 0)\n",
    "        return min(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToMakeZigzag(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n==1: return 0\n",
    "        #\n",
    "        s1,s2 = 0,0\n",
    "        for i in range(n):\n",
    "            if i%2==1:\n",
    "                if i==n-1:\n",
    "                    s1 += max((nums[i] - nums[i-1] + 1), 0)\n",
    "                else:\n",
    "                    s1 += max(max((nums[i]-nums[i-1]+1),\n",
    "                         (nums[i]-nums[i+1]+1)), 0)\n",
    "                pass\n",
    "            else:\n",
    "                if i==0:\n",
    "                    s2 += max((nums[i]-nums[i+1]+1), 0)\n",
    "                elif i==n-1:\n",
    "                    s2 += max((nums[i]-nums[i-1]+1), 0)\n",
    "                else:\n",
    "                    s2 += max(max((nums[i]-nums[i-1]+1),\n",
    "                         (nums[i]-nums[i+1]+1)), 0)\n",
    "                pass\n",
    "            pass\n",
    "        return min(s1,s2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToMakeZigzag(self, nums: List[int]) -> int:\n",
    "        s = [0] * 2\n",
    "        for i, x in enumerate(nums):\n",
    "            left = nums[i - 1] if i else inf\n",
    "            right = nums[i + 1] if i < len(nums) - 1 else inf\n",
    "            s[i % 2] += max(x - min(left, right) + 1, 0)\n",
    "        return min(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToMakeZigzag(self, nums: List[int]) -> int:\n",
    "        s=[0]*2\n",
    "        for i,x in enumerate(nums):\n",
    "            left=nums[i-1] if i else inf\n",
    "            right=nums[i+1] if i<len(nums)-1 else inf\n",
    "            s[i%2] +=max(x-min(left,right)+1,0)\n",
    "        return min(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToMakeZigzag(self, nums: List[int]) -> int:\n",
    "        size = len(nums)\n",
    "\n",
    "        dp = [0, 0]  # nums[0]<nums[1] ; nums[0]>nums[1]\n",
    "\n",
    "        for i in range(size):\n",
    "            # 只调整需要每个最小值的情况即可\n",
    "            if i % 2 == 0:\n",
    "                dp[0] += max(nums[i] - nums[i - 1] + 1 if i > 0 and nums[i] >= nums[i - 1] else 0,\n",
    "                             nums[i] - nums[i + 1] + 1 if i < size - 1 and nums[i] >= nums[i + 1] else 0)\n",
    "            else:\n",
    "                dp[1] += max(nums[i] - nums[i - 1] + 1 if nums[i] >= nums[i - 1] else 0,\n",
    "                             nums[i] - nums[i + 1] + 1 if i < size - 1 and nums[i] >= nums[i + 1] else 0)\n",
    "\n",
    "        return min(dp[0], dp[1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToMakeZigzag(self, nums: List[int]) -> int:\n",
    "        s = [0] * 2\n",
    "        \n",
    "        for i, x in enumerate(nums):\n",
    "            left = nums[i -1] if i else inf\n",
    "            right = nums[i + 1] if i < len(nums) - 1 else inf\n",
    "            s[i % 2] += max(x - (min(left, right) - 1), 0)\n",
    "        \n",
    "        return min(s)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToMakeZigzag(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n <=1:\n",
    "            return 0\n",
    "        \n",
    "        #先上升\n",
    "        cnt = [0,0]\n",
    "\n",
    "        for i in range(n):\n",
    "            if i == 0:\n",
    "                left = inf\n",
    "            else :\n",
    "                left = nums[i-1]\n",
    "            if i == n-1:\n",
    "                right = inf\n",
    "            else:\n",
    "                right = nums[i+1]\n",
    "            \n",
    "            cnt[i%2] += max(nums[i] - min(left, right) + 1, 0)\n",
    "        return min(cnt)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToMakeZigzag(self, nums: List[int]) -> int:\n",
    "        # 两种锯齿数组分别计算。\n",
    "        # 如果是偶数在谷底，那么奇数位置的数值不用降低，只需要考虑偶数位置低于两端即可\n",
    "        # 如果是奇数在谷底，同上，偶数位置的数值不用降低。\n",
    "        n = len(nums)\n",
    "        if n==1: return 0\n",
    "        s1,s2 = 0,0\n",
    "        for i in range(n):\n",
    "            if i%2==1:\n",
    "                if i==n-1:\n",
    "                    s1 += max((nums[i] - nums[i-1] + 1), 0)\n",
    "                else:\n",
    "                    s1 += max(max((nums[i]-nums[i-1]+1),\n",
    "                         (nums[i]-nums[i+1]+1)), 0)\n",
    "                pass\n",
    "            else:\n",
    "                if i==0:\n",
    "                    s2 += max((nums[i]-nums[i+1]+1), 0)\n",
    "                elif i==n-1:\n",
    "                    s2 += max((nums[i]-nums[i-1]+1), 0)\n",
    "                else:\n",
    "                    s2 += max(max((nums[i]-nums[i-1]+1),\n",
    "                         (nums[i]-nums[i+1]+1)), 0)\n",
    "                pass\n",
    "            pass\n",
    "        return min(s1,s2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToMakeZigzag(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        def get(arr, i):\n",
    "            return inf if i < 0 or i >= n else arr[i]\n",
    "        evenAns = 0\n",
    "        for i in range(0, n, 2):\n",
    "            prev, after = get(nums, i-1), get(nums, i+1)\n",
    "            if prev > nums[i] < after:\n",
    "                continue\n",
    "            else:\n",
    "                evenAns += nums[i] - min(prev, after) + 1\n",
    "                \n",
    "        oddAns = 0\n",
    "        for i in range(1, n, 2):\n",
    "            prev, after = get(nums, i-1), get(nums, i+1)\n",
    "            if prev > nums[i] < after:\n",
    "                continue\n",
    "            else:\n",
    "                oddAns += nums[i] - min(prev, after) + 1\n",
    "        return min(oddAns, evenAns)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToMakeZigzag(self, nums: List[int]) -> int:\n",
    "        def help(x):\n",
    "            res = 0\n",
    "            for i in range(x, len(nums), 2):\n",
    "                a = 0\n",
    "                if i - 1 >= 0:\n",
    "                    a = max(a, nums[i] - nums[i-1] + 1)\n",
    "                if i + 1 < len(nums):\n",
    "                    a = max(a, nums[i] - nums[i+1] + 1)\n",
    "                res += a\n",
    "            return res\n",
    "        return min(help(0), help(1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToMakeZigzag(self, nums: List[int]) -> int:\n",
    "        def help(pos: int) -> int:\n",
    "            res = 0\n",
    "            for i in range(pos, len(nums), 2):\n",
    "                a = 0\n",
    "                if i - 1 >= 0:\n",
    "                    a = max(a, nums[i] - nums[i - 1] + 1)\n",
    "                if i + 1 < len(nums):\n",
    "                    a = max(a, nums[i] - nums[i + 1] + 1)\n",
    "                res += a\n",
    "            return res\n",
    "\n",
    "        return min(help(0), help(1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToMakeZigzag(self, nums: List[int]) -> int:\n",
    "        cnt = 0\n",
    "        n = len(nums)\n",
    "        for i in range(0, n, 2):\n",
    "            cur = -1\n",
    "            if i > 0:   cur = max(cur, nums[i] - nums[i-1])\n",
    "            if i < n - 1:   cur = max(cur, nums[i] - nums[i+1])\n",
    "            cnt += cur + 1\n",
    "        \n",
    "        ans = cnt\n",
    "        cnt = 0\n",
    "        for i in range(1, n, 2):\n",
    "            cur = -1\n",
    "            if i > 0:   cur = max(cur, nums[i] - nums[i-1])\n",
    "            if i < n - 1:   cur = max(cur, nums[i] - nums[i+1])\n",
    "            cnt += cur + 1\n",
    "        return min(cnt, ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.nums=[]\n",
    "    def helper(self,pos):\n",
    "        res=0\n",
    "        for i in range(pos,len(self.nums),2):\n",
    "            a=0\n",
    "            if i-1>=0:\n",
    "                a=max(a,self.nums[i]-self.nums[i-1]+1)\n",
    "            if i+1<len(self.nums):\n",
    "                a=max(a,self.nums[i]-self.nums[i+1]+1)\n",
    "            res+=a\n",
    "        return res\n",
    "    def movesToMakeZigzag(self, nums: List[int]) -> int:\n",
    "        self.nums=nums\n",
    "        return min (self.helper(0),self.helper(1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToMakeZigzag(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n <= 2:\n",
    "            return 0\n",
    "        def f(begin):\n",
    "            ans = 0\n",
    "            for i in range(begin, n, 2):\n",
    "                if i == 0:\n",
    "                    ans += max(0, nums[i]-nums[i+1]+1)\n",
    "                elif i == n-1:\n",
    "                    ans += max(0, nums[i]-nums[i-1]+1)\n",
    "                else:\n",
    "                    ans += max(0, nums[i]-nums[i-1]+1, nums[i]-nums[i+1]+1)\n",
    "            return ans\n",
    "        return min(f(0), f(1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToMakeZigzag(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        cnt = 0\n",
    "        ans = inf\n",
    "        for i in range(1, n, 2):\n",
    "            pre, end = i - 1, i + 1\n",
    "            mi = float('inf')\n",
    "            if pre >= 0:\n",
    "                mi = min(nums[pre], mi)\n",
    "            if end < n:\n",
    "                mi = min(mi, nums[end])\n",
    "            if mi <= nums[i]:\n",
    "                cnt += nums[i] - mi + 1\n",
    "            \n",
    "        ans = cnt\n",
    "        cnt = 0\n",
    "        \n",
    "        for i in range(0, n, 2):\n",
    "            pre, end = i - 1, i + 1\n",
    "            mi = float('inf')\n",
    "            if pre >= 0:\n",
    "                mi = min(nums[pre], mi)\n",
    "            if end < n:\n",
    "                mi = min(mi, nums[end])\n",
    "            if mi <= nums[i]:\n",
    "                cnt += nums[i] - mi + 1\n",
    "        ans = min(ans, cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToMakeZigzag(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(1, n, 2):\n",
    "            a, b = nums[i-1], nums[i+1] if i+1<n else inf\n",
    "            c= nums[i]\n",
    "            low = min(a, b)\n",
    "            if c >= low:\n",
    "                ans += c-low+1\n",
    "        \n",
    "        ans2 = 0\n",
    "        for i in range(0, n, 2):\n",
    "            a, b = nums[i-1] if i else inf, nums[i+1] if i+1<n else inf\n",
    "            c= nums[i]\n",
    "            low = min(a, b)\n",
    "            if c >= low:\n",
    "                ans2 += c-low+1\n",
    "        \n",
    "        return min(ans, ans2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToMakeZigzag(self, nums: List[int]) -> int:\n",
    "        s = [0] * 2\n",
    "        for i, x in enumerate(nums):\n",
    "            left = nums[i - 1] if i else inf\n",
    "            right = nums[i + 1] if i < len(nums) - 1 else inf\n",
    "            s[i % 2] += max(x - min(left, right) + 1, 0)\n",
    "        return min(s)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToMakeZigzag(self, nums: List[int]) -> int:\n",
    "        # 最小操作次数不会同时出现调整奇数位置和偶数位置的情况\n",
    "        n=len(nums)\n",
    "        if n==1:\n",
    "            return 0\n",
    "\n",
    "        odd_sum=0\n",
    "        even_sum=0\n",
    "        i=0\n",
    "        while i<n:\n",
    "            if i==0:\n",
    "                odd_sum+=max(0,nums[i]-nums[i+1]+1)\n",
    "            elif i==n-1:\n",
    "                odd_sum+=max(0,nums[i]-nums[i-1]+1)\n",
    "            else:\n",
    "                odd_sum+=max(0,nums[i]-nums[i-1]+1,nums[i]-nums[i+1]+1)\n",
    "            i+=2\n",
    "        i=1\n",
    "        while i<n:\n",
    "            if i==n-1:\n",
    "                even_sum+=max(0,nums[i]-nums[i-1]+1)\n",
    "            else:\n",
    "                even_sum+=max(0,nums[i]-nums[i-1]+1,nums[i]-nums[i+1]+1)\n",
    "            i+=2\n",
    "        return min(odd_sum,even_sum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToMakeZigzag(self, nums: List[int]) -> int:\n",
    "        def f(pos: int) -> int:\n",
    "            res = 0\n",
    "            n = len(nums)\n",
    "            for i in range(pos, n, 2):\n",
    "                tmp = 0\n",
    "                if i - 1 >= 0:\n",
    "                    tmp = max(tmp, nums[i] - nums[i - 1] + 1)\n",
    "                if i + 1 < n:\n",
    "                    tmp = max(tmp, nums[i] - nums[i + 1] + 1)\n",
    "                res += tmp\n",
    "            return res\n",
    "        return min(f(0), f(1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToMakeZigzag(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0 \n",
    "        if (n-1)%2==1:\n",
    "            nums.append(float(\"inf\"))\n",
    "            nums.insert(0,float(\"inf\"))\n",
    "        else:\n",
    "            nums.append(float(\"-inf\"))\n",
    "            nums.insert(0,float(\"-inf\"))            \n",
    "        for i in range(2,n+1,2):\n",
    "            #print(ans,nums)\n",
    "            t = min(nums[i-1],nums[i+1])\n",
    "            if nums[i]>=t:\n",
    "                ans += (nums[i]-t+1)\n",
    "        ans2 = 0\n",
    "        nums[0] = float(\"inf\")\n",
    "        nums[-1] = -nums[-1]\n",
    "        for i in range(1,n+1,2):\n",
    "            t = min(nums[i-1],nums[i+1])\n",
    "            if nums[i]>=t:\n",
    "                ans2 += (nums[i]-t+1)\n",
    "        print(ans,ans2)\n",
    "        return min(ans,ans2)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToMakeZigzag(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        evenMove, oddMove = 0,0\n",
    "        start = 1\n",
    "        even = deepcopy(nums)\n",
    "        odd = deepcopy(nums)\n",
    "        while start < n:\n",
    "            if start-1 >=0 and even[start] <= even[start-1]:\n",
    "                evenMove += even[start-1]-even[start]+1\n",
    "                even[start-1] = even[start]-1\n",
    "            if start+1 < n and even[start] <= even[start+1]:\n",
    "                evenMove += even[start+1]-even[start]+1\n",
    "                even[start+1] = even[start]-1\n",
    "            start += 2\n",
    "        start = 0\n",
    "        while start < n:\n",
    "            if start-1 >=0 and odd[start] <= odd[start-1]:\n",
    "                oddMove += odd[start-1]-odd[start]+1\n",
    "                odd[start-1] = odd[start]-1\n",
    "            if start+1 < n and odd[start] <= odd[start+1]:\n",
    "                oddMove += odd[start+1]-odd[start]+1\n",
    "                odd[start+1] = odd[start]-1\n",
    "            start += 2\n",
    "        print(oddMove, evenMove)\n",
    "        return min(oddMove, evenMove)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToMakeZigzag(self, nums: List[int]) -> int:\n",
    "        # 统计2种情况需要改变的数，选择较小值即可\n",
    "        n = len(nums)\n",
    "\n",
    "        # 偶数大\n",
    "        a = 0\n",
    "        l = nums.copy()\n",
    "        for i in range(1, n):\n",
    "            if i & 1:\n",
    "                if l[i] >= l[i - 1]:\n",
    "                    a += l[i] - l[i - 1] + 1\n",
    "                    l[i] = l[i - 1] - 1\n",
    "            elif l[i] <= l[i - 1]:\n",
    "                a += l[i - 1] - l[i] + 1\n",
    "\n",
    "        # 奇数大\n",
    "        b = 0\n",
    "        l = nums.copy()\n",
    "        for i in range(1, n):\n",
    "            if i & 1:\n",
    "                if l[i] <= l[i - 1]:\n",
    "                    b += l[i - 1] - l[i] + 1\n",
    "            elif l[i] >= l[i - 1]:\n",
    "                b += l[i] - l[i - 1] + 1\n",
    "                l[i] = l[i - 1] - 1\n",
    "        \n",
    "        return min(a, b)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToMakeZigzag(self, nums: List[int]) -> int:\n",
    "        #copy\n",
    "        s =[0]*2\n",
    "        for i,x in enumerate(nums):\n",
    "            left = nums[i-1] if i else inf\n",
    "            right = nums[i+1] if i <len(nums)-1 else inf\n",
    "            s[i%2] += max(x-min(left,right) + 1,0)\n",
    "        return min(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToMakeZigzag(self, nums: List[int]) -> int:\n",
    "        # 贪心 + 分类讨论\n",
    "        res = [0] * 2\n",
    "        \n",
    "        for i, x in enumerate(nums):\n",
    "            left = nums[i - 1] if i >= 1 else inf\n",
    "            right = nums[i + 1] if i <= len(nums) - 2 else inf\n",
    "            res[i % 2] += max(x - min(left, right) + 1, 0) \n",
    "        \n",
    "        return min(res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToMakeZigzag(self, nums: List[int]) -> int:\n",
    "        # 一个数组变成锯齿数组只有两种情况\n",
    "        # 1. 奇数大 | 2. 偶数大\n",
    "        \n",
    "        length = len(nums)\n",
    "\n",
    "        if length == 1:\n",
    "            return 0\n",
    "\n",
    "        def get_min(i):\n",
    "            if i == 0:\n",
    "                return nums[i+1]\n",
    "            elif i == length - 1:\n",
    "                return nums[i-1]\n",
    "            else:\n",
    "                return min(nums[i-1], nums[i+1])\n",
    "        \n",
    "        def get_gap(_i):\n",
    "            gap = nums[i] - get_min(i) + 1\n",
    "            if gap < 0:\n",
    "                return 0\n",
    "            else:\n",
    "                return gap\n",
    "        # 偶数波峰\n",
    "        ret_1, ret_2 = 0, 0\n",
    "        for i in range(length):\n",
    "            if i % 2 == 1:\n",
    "                ret_1 += get_gap(i)\n",
    "            else:\n",
    "                ret_2 += get_gap(i)\n",
    "        \n",
    "        return min(ret_1, ret_2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToMakeZigzag(self, nums: List[int]) -> int:\n",
    "        ans = float('inf')\n",
    "        copy = nums.copy()\n",
    "        flag = 1\n",
    "        tmp = 0\n",
    "        for i in range(1, len(nums)):\n",
    "            if flag:\n",
    "                if nums[i] <= nums[i - 1]:\n",
    "                    tmp += nums[i - 1] - (nums[i] - 1)\n",
    "            else:\n",
    "                if nums[i] >= nums[i - 1]:\n",
    "                    tmp += nums[i] - (nums[i - 1] - 1)\n",
    "                    nums[i] = nums[i - 1] - 1\n",
    "\n",
    "            flag ^= 1\n",
    "        \n",
    "        ans = min(ans, tmp)\n",
    "        nums = copy\n",
    "        print(ans)\n",
    "        flag = 0\n",
    "        tmp = 0\n",
    "        for i in range(1, len(nums)):\n",
    "            if flag:\n",
    "                if nums[i] <= nums[i - 1]:\n",
    "                    tmp += nums[i - 1] - (nums[i] - 1)\n",
    "            else:\n",
    "                if nums[i] >= nums[i - 1]:\n",
    "                    tmp += nums[i] - (nums[i - 1] - 1)\n",
    "                    nums[i] = nums[i - 1] - 1\n",
    "\n",
    "            flag ^= 1\n",
    "\n",
    "        return min(ans, tmp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToMakeZigzag(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        if n<=1:\n",
    "            return 0\n",
    "        dp=[[0,0] for _ in range(n)]\n",
    "        if nums[0]>=nums[1]:\n",
    "            dp[0][1]=nums[0]-nums[1]+1\n",
    "        for i in range(1,n):\n",
    "            h=nums[i-1]\n",
    "            dp[i][0]=dp[i-1][1]\n",
    "            dp[i][1]=dp[i-1][0]\n",
    "            if i<n-1:\n",
    "                h=min(h,nums[i+1])\n",
    "            if h<=nums[i]:\n",
    "                dp[i][1]+=nums[i]-h+1\n",
    "        return min(dp[-1])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToMakeZigzag(self, nums):\n",
    "        s = [0] * 2\n",
    "        for i, x in enumerate(nums):\n",
    "            left = nums[i - 1] if i else inf\n",
    "            right = nums[i + 1] if i < len(nums) - 1 else inf\n",
    "            s[i % 2] += max(x - min(left, right) + 1, 0)\n",
    "        return min(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToMakeZigzag(self, nums: List[int]) -> int:\n",
    "        cnt = 0\n",
    "        n = len(nums)\n",
    "        for i in range(0, n, 2):\n",
    "            cur = -1\n",
    "            if i > 0:   cur = max(cur, nums[i] - nums[i-1])\n",
    "            if i < n - 1:   cur = max(cur, nums[i] - nums[i+1])\n",
    "            cnt += cur + 1\n",
    "        \n",
    "        ans = cnt\n",
    "        cnt = 0\n",
    "        for i in range(1, n, 2):\n",
    "            cur = -1\n",
    "            if i > 0:   cur = max(cur, nums[i] - nums[i-1])\n",
    "            if i < n - 1:   cur = max(cur, nums[i] - nums[i+1])\n",
    "            cnt += cur + 1\n",
    "        return min(cnt, ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToMakeZigzag(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] * 2\n",
    "        for i, x in enumerate(nums):\n",
    "            left = nums[i-1] if i else inf\n",
    "            right = nums[i+1] if i<n-1 else inf\n",
    "            dp[i%2] += max(x - min(left,right) + 1, 0)\n",
    "        return min(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToMakeZigzag(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n <=1:\n",
    "            return 0\n",
    "        \n",
    "        #先上升\n",
    "        cnt1 = 0\n",
    "        for i in range(0,n,2):\n",
    "            if i == 0:\n",
    "                if nums[i]>=nums[i+1]:\n",
    "                    cnt1 += nums[i]-(nums[i+1]-1)\n",
    "            elif i == n-1:\n",
    "                if nums[i]>=nums[i-1]:\n",
    "                    cnt1 += nums[i]-(nums[i-1]-1)\n",
    "            else:\n",
    "                if nums[i]<nums[i-1] and nums[i]<nums[i+1]:\n",
    "                    continue\n",
    "                minnum = min(nums[i-1],nums[i+1])\n",
    "                cnt1 += nums[i]-(minnum-1)\n",
    "        # 先下降\n",
    "        cnt2 = 0\n",
    "        for i in range(1,n,2):\n",
    "            if i == n-1:\n",
    "                if nums[i]>=nums[i-1]:\n",
    "                    cnt2 += nums[i]-(nums[i-1]-1)\n",
    "            else:\n",
    "                if nums[i]<nums[i-1] and nums[i]<nums[i+1]:\n",
    "                    continue\n",
    "                minnum = min(nums[i-1],nums[i+1])\n",
    "                cnt2 += nums[i]-(minnum-1)\n",
    "        return min(cnt1,cnt2)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def movesToMakeZigzag(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        # 计算两种情况所需的操作数\n",
    "        res1, res2 = 0, 0\n",
    "\n",
    "        # 检查偶数索引的情况\n",
    "        for i in range(0, n, 2):\n",
    "            left = nums[i - 1] if i - 1 >= 0 else float('inf')\n",
    "            right = nums[i + 1] if i + 1 < n else float('inf')\n",
    "            # 如果当前值大于或等于相邻的最小值，我们需要进行操作\n",
    "            if nums[i] >= min(left, right):\n",
    "                res1 += nums[i] - min(left, right) + 1\n",
    "\n",
    "        # 检查奇数索引的情况\n",
    "        for i in range(1, n, 2):\n",
    "            left = nums[i - 1]\n",
    "            right = nums[i + 1] if i + 1 < n else float('inf')\n",
    "            # 如果当前值大于或等于相邻的最小值，我们需要进行操作\n",
    "            if nums[i] >= min(left, right):\n",
    "                res2 += nums[i] - min(left, right) + 1\n",
    "\n",
    "        return min(res1, res2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToMakeZigzag(self, nums: List[int]) -> int:\n",
    "        def help(pos: int) -> int:\n",
    "            res = 0\n",
    "            for i in range(pos, len(nums), 2):\n",
    "                a = 0\n",
    "                if i - 1 >= 0:\n",
    "                    a = max(a, nums[i] - nums[i - 1] + 1)\n",
    "                if i + 1 < len(nums):\n",
    "                    a = max(a, nums[i] - nums[i + 1] + 1)\n",
    "                res += a\n",
    "            return res\n",
    "\n",
    "        return min(help(0), help(1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToMakeZigzag(self, nums: List[int]) -> int:\n",
    "        ans = float('inf')\n",
    "        copy = nums.copy()\n",
    "        flag = 1\n",
    "        tmp = 0\n",
    "        for i in range(1, len(nums)):\n",
    "            if flag:\n",
    "                if nums[i] <= nums[i - 1]:\n",
    "                    tmp += nums[i - 1] - (nums[i] - 1)\n",
    "                    # nums[i - 1] = nums[i - 1] - (nums[i] - 1)\n",
    "            else:\n",
    "                if nums[i] >= nums[i - 1]:\n",
    "                    tmp += nums[i] - (nums[i - 1] - 1)\n",
    "                    nums[i] = nums[i - 1] - 1\n",
    "\n",
    "            flag ^= 1\n",
    "        \n",
    "        ans = min(ans, tmp)\n",
    "        nums = copy\n",
    "        print(ans)\n",
    "        flag = 0\n",
    "        tmp = 0\n",
    "        for i in range(1, len(nums)):\n",
    "            if flag:\n",
    "                if nums[i] <= nums[i - 1]:\n",
    "                    tmp += nums[i - 1] - (nums[i] - 1)\n",
    "                    # nums[i - 1] = nums[i - 1] - (nums[i] - 1)\n",
    "            else:\n",
    "                if nums[i] >= nums[i - 1]:\n",
    "                    tmp += nums[i] - (nums[i - 1] - 1)\n",
    "                    nums[i] = nums[i - 1] - 1\n",
    "\n",
    "            flag ^= 1\n",
    "\n",
    "        return min(ans, tmp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToMakeZigzag(self, nums: List[int]) -> int:\n",
    "        def help(pos: int) -> int:\n",
    "            res = 0\n",
    "            for i in range(pos, len(nums), 2):\n",
    "                a = 0\n",
    "                if i - 1 >= 0:\n",
    "                    a = max(a, nums[i] - nums[i - 1] + 1)\n",
    "                if i + 1 < len(nums):\n",
    "                    a = max(a, nums[i] - nums[i + 1] + 1)\n",
    "                res += a\n",
    "            return res\n",
    "\n",
    "        return min(help(0), help(1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToMakeZigzag(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        c1 = c2 = 0\n",
    "        if n > 1 and nums[0] >= nums[1]:\n",
    "            c2 = nums[0] - nums[1] + 1\n",
    "        for i in range(1, n):\n",
    "            if i == n - 1:\n",
    "                t = nums[i - 1] - 1\n",
    "            else:\n",
    "                t = min(nums[i - 1], nums[i + 1]) - 1\n",
    "\n",
    "            if i % 2 == 1:\n",
    "                c1 += 0 if nums[i] <= t else nums[i] - t\n",
    "            else:\n",
    "                c2 += 0 if nums[i] <= t else nums[i] - t\n",
    "        return min(c1, c2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToMakeZigzag(self, nums: List[int]) -> int:\n",
    "            \n",
    "        def help(pos: int) -> int:\n",
    "            res = 0\n",
    "            for i in range(pos, len(nums), 2):\n",
    "                a = 0\n",
    "                if i - 1 >= 0:\n",
    "                    a = max(a, nums[i] - nums[i - 1] + 1)\n",
    "                if i + 1 < len(nums):\n",
    "                    a = max(a, nums[i] - nums[i + 1] + 1)\n",
    "                res += a\n",
    "            return res\n",
    "\n",
    "        return min(help(0), help(1))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToMakeZigzag(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        @lru_cache(None)\n",
    "        def dfs(i: int, cur: int, inc: bool):\n",
    "            if i == n - 1:\n",
    "                return 0\n",
    "            if inc and cur >= nums[i + 1]:\n",
    "                return cur - (nums[i + 1] - 1) + dfs(i + 1, nums[i + 1], not inc)\n",
    "            elif not inc and cur <= nums[i + 1]:\n",
    "                return nums[i + 1] - (cur - 1) + dfs(i + 1, cur - 1, not inc)\n",
    "            else:\n",
    "                return dfs(i + 1, nums[i + 1], not inc)\n",
    "        res1 = dfs(0, nums[0], True)\n",
    "        dfs.cache_clear()\n",
    "        res2 = dfs(0, nums[0], False)\n",
    "        dfs.cache_clear()\n",
    "        return min(res1, res2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def movesToMakeZigzag(self, nums: List[int]) -> int:\n",
    "        \n",
    "                \n",
    "                \n",
    "                \n",
    "                def solve(jntm,nums):\n",
    "                    ans = 0;n = len(nums)\n",
    "                    s = sum(nums)\n",
    "                    for i in range(n):\n",
    "                        if i % 2 == jntm:\n",
    "                            if i and nums[i-1] >= nums[i]:\n",
    "                                ans += nums[i-1] - nums[i] + 1\n",
    "                                nums[i-1] = nums[i] - 1\n",
    "                            if i + 1 < n and nums[i+1] >= nums[i]:\n",
    "                                ans += nums[i+1] - nums[i] + 1\n",
    "                                nums[i+1] = nums[i] - 1\n",
    "                    return ans\n",
    "                t = nums.copy()\n",
    "                return min(solve(1,nums),solve(0,t))"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
